#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_V 6 // 顶点数（A-F）
#define INF INT_MAX

// 邻接矩阵表示
typedef struct
{
    int vertices[MAX_V][MAX_V]; // 邻接矩阵
    char vertexNames[MAX_V];    // 顶点名称
    int vCount;                 // 顶点数
} Graph;

// 创建图
Graph *createGraph()
{
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->vCount = 0;

    // 初始化邻接矩阵
    for (int i = 0; i < MAX_V; i++)
    {
        for (int j = 0; j < MAX_V; j++)
        {
            g->vertices[i][j] = (i == j) ? 0 : INF;
        }
    }
    return g;
}

// 添加顶点
void addVertex(Graph *g, char name)
{
    if (g->vCount >= MAX_V)
    {
        printf("Error: Graph is full\n");
        return;
    }
    g->vertexNames[g->vCount++] = name;
}

// 添加带权边（无向图）
void addEdge(Graph *g, int v1, int v2, int weight)
{
    if (v1 < 0 || v1 >= g->vCount || v2 < 0 || v2 >= g->vCount)
    {
        printf("Error: Invalid vertex index\n");
        return;
    }
    g->vertices[v1][v2] = weight;
    g->vertices[v2][v1] = weight;
}

// Prim算法实现
void primMST(Graph *g)
{
    int parent[MAX_V]; // 存储生成树
    int key[MAX_V];    // 存储边的权值
    int inMST[MAX_V];  // 标记顶点是否在MST中

    // 初始化
    for (int i = 0; i < g->vCount; i++)
    {
        key[i] = INF;
        inMST[i] = 0;
    }

    // 从第一个顶点开始
    key[0] = 0;
    parent[0] = -1; // 根结点

    for (int count = 0; count < g->vCount - 1; count++)
    {
        // 选取key值最小的顶点
        int minKey = INF, minIndex = -1;
        for (int v = 0; v < g->vCount; v++)
        {
            if (!inMST[v] && key[v] < minKey)
            {
                minKey = key[v];
                minIndex = v;
            }
        }

        // 将选中的顶点加入MST
        inMST[minIndex] = 1;

        // 更新相邻顶点的key值
        for (int v = 0; v < g->vCount; v++)
        {
            if (g->vertices[minIndex][v] && !inMST[v] &&
                g->vertices[minIndex][v] < key[v])
            {
                parent[v] = minIndex;
                key[v] = g->vertices[minIndex][v];
            }
        }
    }

    // 打印最小生成树
    printf("Minimum Spanning Tree (Prim's Algorithm):\n");
    int totalWeight = 0;
    for (int i = 1; i < g->vCount; i++)
    {
        printf("%c - %c : %d\n",
               g->vertexNames[parent[i]],
               g->vertexNames[i],
               g->vertices[i][parent[i]]);
        totalWeight += g->vertices[i][parent[i]];
    }
    printf("Total Weight: %d\n", totalWeight);
}

// 销毁图
void destroyGraph(Graph *g)
{
    free(g);
}

int main()
{
    // 创建图
    Graph *g = createGraph();

    // 添加顶点（A-F）
    addVertex(g, 'A');
    addVertex(g, 'B');
    addVertex(g, 'C');
    addVertex(g, 'D');
    addVertex(g, 'E');
    addVertex(g, 'F');

    // 添加带权边（按照题目要求）
    addEdge(g, 0, 1, 1); // A-B 1
    addEdge(g, 0, 2, 4); // A-C 4
    addEdge(g, 0, 3, 4); // A-D 4
    addEdge(g, 0, 4, 6); // A-E 6
    addEdge(g, 0, 5, 5); // A-F 5
    addEdge(g, 1, 2, 5); // B-C 5
    addEdge(g, 2, 3, 2); // C-D 2
    addEdge(g, 3, 4, 6); // D-E 6
    addEdge(g, 4, 5, 3); // E-F 3
    addEdge(g, 5, 1, 6); // F-B 6

    // 计算并打印最小生成树
    primMST(g);

    // 销毁图
    destroyGraph(g);

    return 0;
}